For a number of applications, a problem of determining the minimum or the maximum, of a finitely long sequence of elements in a privacy preserving manner is important. For example, the elements are sensitive biometric, medical, scientific, technical, financial, or commercial data.
The problem is defined as follows. A first processor stores a sequence of encrypted elements. The first processor interacts with a second processor to determine the encryption of, e.g., the minimum element, in the sequence. The requirement of the problem is that the value and the index of the minimum element are not discovered by any processor.
This particular problem arises in many secure multiparty computation methods. For example, the first processor has a database of binary fingerprint feature vectors and the second processor has a single encrypted fingerprint feature vector. Then, the first processor, using a secure multiparty computation method, determines encrypted Hamming distances between the single feature vector of the second processor and each feature vector in the database. Thus, the first processor obtains a vector of encrypted Hamming distances. Next, the encryption of the minimum Hamming distance is determined to locate the fingerprint feature vector in the database most similar to the first feature vector.
Accordingly, there is a need for selecting an encrypted element in an encrypted vector according to an ordering of the encrypted elements in the encrypted vector.